package Algorithm;

import java.util.Arrays;

/**
 * @author Lzm
 * @version 1.0
 */
public class KMPAlgorithm {
  public static void main(String[] args) {
    String str = "leeto";

    String haystack  = "leetcode";


  }

  public int strStr(String haystack, String needle) {
    int[] next = getNext(needle);
    for(int i = 0 , j = 0 ; i < haystack.length() ; i ++){
      while(j > 0 && haystack.charAt(i) != needle.charAt(j)){
        j = next[j - 1];
      }
      if (haystack.charAt(i) == needle.charAt(j)){
        j++;
      }
      if (j == needle.length()){
        return i - needle.length() + 1;
      }
    }
    return -1;
  }

  /*得到部分匹配值 next数组*/
  public static int[] getNext(String needle){
    /*初始化*/
    int[] next = new int[needle.length()];
    next[0] = 0;
    /*循环遍历*/
    for(int i = 1 , j = 0 ; i < needle.length() ; i ++){
      /*i和j字符不同*/
      while(j > 0 && needle.charAt(i) != needle.charAt(j)){
        j = next[j - 1];
      }
      /*i和j字符相同*/
      if (needle.charAt(i) == needle.charAt(j)){
        j++;
      }

      next[i] = j;
    }
    return next;
  }
}
